/**
 * 
 */
package leetCode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @author zhong
 *
 */
public class SlidingPuzzle {

	public int slidingPuzzle(int[][] board) {
		String target = "123450";

		StringBuilder sBuilder = new StringBuilder();
		int pos0 = -1;
		for (int i = 0; i < 6; i++) {
			int val = board[i / 3][i % 3];
			if (val == 0)
				pos0 = i;
			sBuilder.append(val);
		}
		Set<String> visited = new HashSet<>();
		Queue<String> queue = new LinkedList<>();
		Queue<Integer> pos = new LinkedList<>();
		queue.add((target));
		visited.add(target);
		pos.add(5);
		String start = sBuilder.toString();
		int deep = 0;
		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				String cur = queue.poll();
				if (cur.equals(start)) {
					return deep;
				}
				pos0 = pos.poll();
				int newPos = -1;
				if (pos0 < 3) {// 下
					newPos = pos0 + 3;
				} else {// 上
					newPos = pos0 - 3;
				}
				StringBuilder sBuilder2 = new StringBuilder(cur);
				String string;
				sBuilder2.setCharAt(pos0, sBuilder2.charAt(newPos));
				sBuilder2.setCharAt(newPos, '0');
				string = sBuilder2.toString();
				if (visited.add(string)) {
					queue.offer(sBuilder2.toString());
					pos.offer(newPos);
				}
				if (pos0 % 3 != 0) {
					newPos = pos0 - 1;
					sBuilder2 = new StringBuilder(cur);
					sBuilder2.setCharAt(pos0, sBuilder2.charAt(newPos));
					sBuilder2.setCharAt(newPos, '0');
					string = sBuilder2.toString();
					if (visited.add(string)) {
						queue.offer(sBuilder2.toString());
						pos.offer(newPos);
					}
				}
				if (pos0 % 3 != 2) {
					newPos = pos0 + 1;
					sBuilder2 = new StringBuilder(cur);
					sBuilder2.setCharAt(pos0, sBuilder2.charAt(newPos));
					sBuilder2.setCharAt(newPos, '0');
					string = sBuilder2.toString();
					if (visited.add(string)) {
						queue.offer(sBuilder2.toString());
						pos.offer(newPos);
					}
				}
			}
			deep++;
		}
		return -1;
	}

	// private int BFS(String start, Map<String, Integer> memo, Queue<StringBuilder>
	// queue, int pos0) {
	// StringBuilder sBuilder3 = queue.poll();
	// String input = sBuilder3.toString();
	// if (input.equals(start)) {
	// return 0;
	// }
	// if (memo.containsKey(input)) {
	// if (memo.get(input) == -1) {// 已经访问过，但还没计算出来
	// return Integer.MAX_VALUE;
	// }
	// return memo.get(input);
	// }
	// memo.put(input, -1);
	// // 堆0所在位置尝试可以进行的操作
	// StringBuilder sBuilder = new StringBuilder(sBuilder3);
	//
	// int newPos = -1;
	// if (pos0 < 3) {// 下
	// newPos = pos0 + 3;
	// } else {// 上
	// newPos = pos0 - 3;
	// }
	// sBuilder.setCharAt(pos0, sBuilder.charAt(newPos));
	// sBuilder.setCharAt(newPos, '0');
	// int res = Integer.MAX_VALUE;
	// res = Math.min(res, BFS(memo, sBuilder, newPos));
	// if (pos0 % 3 != 0) {
	// newPos = pos0 - 1;
	// StringBuilder sBuilder2 = new StringBuilder(sBuilder3);
	// sBuilder2.setCharAt(pos0, sBuilder2.charAt(newPos));
	// sBuilder2.setCharAt(newPos, '0');
	// res = Math.min(res, BFS(memo, sBuilder2, newPos));
	// }
	// if (pos0 % 3 != 2) {
	// newPos = pos0 + 1;
	// StringBuilder sBuilder2 = new StringBuilder(sBuilder3);
	// sBuilder2.setCharAt(pos0, sBuilder2.charAt(newPos));
	// sBuilder2.setCharAt(newPos, '0');
	// res = Math.min(res, BFS(memo, sBuilder2, newPos));
	// }
	// if (res != Integer.MAX_VALUE) {
	// res++;
	// }
	// memo.put(input, res);
	// return res;
	// }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[][] board = { { 4, 1, 2 }, { 5, 0, 3 } };
		// { 4, 1, 2 }, { 5, 0, 3 }
		// { 1, 2, 3 }, { 4, 0, 5 }
		// { 1, 2, 3 }, { 5, 4, 0 }
		// { 3, 2, 4 }, { 1, 5, 0 }
		System.out.println(new SlidingPuzzle().slidingPuzzle(board));
	}

}
